|
In the theory of formal languages, the pumping lemma for regular languages describes an essential property of all regular languages. Informally, it says that all sufficiently long words in a regular language may be ''pumped'' — that is, have a middle section of the word repeated an arbitrary number of times — to produce a new word that also lies within the same language. Specifically, the pumping lemma says that for any regular language ''L'' there exists a constant ''p'' such that any word ''w'' in ''L'' with length at least ''p'' can be split into three substrings, ''w'' = ''xyz'', where the middle portion ''y'' must not be empty, such that the words ''xz'', ''xyz'', ''xyyz'', ''xyyyz'', … constructed by repeating ''y'' an arbitrary number of times (including zero times) are still in ''L''. This process of repetition is known as "pumping". Moreover, the pumping lemma guarantees that the length of ''xy'' will be at most ''p'', imposing a limit on the ways in which ''w'' may be split. Finite languages trivially satisfy the pumping lemma by having ''p'' equal to the maximum string length in ''L'' plus one. The pumping lemma is useful for disproving the regularity of a specific language in question. It was first proved by Dana Scott and Michael Rabin in 1959,〔 Here: Lemma 8, p.119〕 and rediscovered shortly after by Yehoshua Bar-Hillel, Micha A. Perles, and Eli Shamir in 1961, as a simplification of their pumping lemma for context-free languages.〔.〕〔 Here: Sect.4.6, p.166〕 == Formal statement == Let ''L'' be a regular language. Then there exists an integer ''p'' ≥ 1 depending only on ''L'' such that every string ''w'' in ''L'' of length at least ''p'' (''p'' is called the "pumping length") can be written as ''w'' = ''xyz'' (i.e., ''w'' can be divided into three substrings), satisfying the following conditions: # |''y''| ≥ 1; # |''xy''| ≤ ''p'' # for all ''i'' ≥ 0, ''xy''i''z'' ∈ ''L'' ''y'' is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in ''L''). (1) means the loop ''y'' to be pumped must be of length at least one; (2) means the loop must occur within the first ''p'' characters. |''x''| must be smaller than ''p'' (conclusion of (1) and (2)), apart from that there is no restriction on ''x'' and ''z''. In simple words, for any regular language L, any sufficiently long word w (in L) can be split into 3 parts. i.e. w = xyz , such that all the strings xykz for k≥0 are also in L. Below is a formal expression of the Pumping Lemma. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Pumping lemma for regular languages」の詳細全文を読む スポンサード リンク
|